package leetcode.editor.week.week305;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;

class Solution6139 {
    public static void main(String[] args) {
        new Solution6139().reachableNodes(7, new int[][]{{0, 1}, {1, 2}, {3, 1}, {4, 0}, {0, 5}, {5, 6}}, new int[]{4, 5});
    }

    // dfs
    /*public int reachableNodes(int n, int[][] edges, int[] restricted) {
        set = new HashSet<>();
        visited = new boolean[n];
        for (int i : restricted) {
            set.add(i);
        }

        LinkedList<Integer>[] tree = new LinkedList[n];
        for (int i = 0; i < n; i++) {
            tree[i] = new LinkedList<>();
        }

        for (int[] edge : edges) {
            int from = edge[0];
            int to = edge[1];
            tree[from].add(to);
            tree[to].add(from);
        }

        for (Integer v : tree[0]) {
            dfs(tree, v);
        }

        return res;
    }

    Set<Integer> set;
    int res = 1;
    boolean[] visited;

    public void dfs(LinkedList<Integer>[] tree, Integer v) {
        if (visited[v] == true  || set.contains(v) || tree[v].size() == 0 || v == 0) {
            return;
        }

        res++;
        visited[v] = true;
        for (Integer m : tree[v]) {
            dfs(tree, m);
        }

    }*/

    // bfs
    Set<Integer> set;
    Queue<Integer> queue;
    boolean[] visited;  // 记录遍历过的路径

    public int reachableNodes(int n, int[][] edges, int[] restricted) {
        set = new HashSet<>();
        visited = new boolean[n];
        queue = new LinkedList<>();
        for (int i : restricted) {
            set.add(i);
        }

        LinkedList<Integer>[] tree = new LinkedList[n];
        for (int i = 0; i < n; i++) {
            tree[i] = new LinkedList<>();
        }

        for (int[] edge : edges) {
            int from = edge[0];
            int to = edge[1];
            tree[from].add(to);
            tree[to].add(from);
        }

        queue.offer(0);
        visited[0] = true;
        int res = 1;
        while (!queue.isEmpty()) {
            Integer poll = queue.poll();
            for (Integer v : tree[poll]) {
                if (!set.contains(v) && visited[v] == false) {
                    res++;
                    visited[v] = true;
                    queue.offer(v);
                }
            }
        }

        return res;
    }

}